package mosdi.fa;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.TreeSet;

/** Represents an alphabet by essentially providing a mapping between
 *  each character and an index, i.e. one may work on the alphabet [0,..,n-1]. */
public class Alphabet implements Iterable<Character> {
	private char[] chars;
	private int[] charIndices;
	
	private boolean useSeparator;
	private char separator;

	public Alphabet(Collection<Character> l) {
		this.useSeparator = false;
		this.separator = 0;
		List<Character> sortedList = new ArrayList<Character>(l);
		Collections.sort(sortedList);
		chars = new char[l.size()];
		charIndices = new int[256];
		Arrays.fill(charIndices, -1);
		int i=0;
		for (char c : sortedList) {
			chars[i]=c;
			charIndices[c]=i;
			++i;
		}
	}
	
	/** Constructs an alphabet that contains all characters occuring in 
	 *  a given string s.
	 */
	public Alphabet(String s) {
		boolean[] charsPresent = new boolean[256];
		int charCount = 0;
		for (int i=0; i<s.length(); ++i) {
			int c = (int)s.charAt(i);
			if (!charsPresent[c]) {
				charsPresent[c] = true;
				charCount+=1;
			}
		}
		chars = new char[charCount];
		charIndices = new int[256];
		Arrays.fill(charIndices, -1);
		int n = 0;
		for (int c=0; c<charsPresent.length; ++c) {
			if (charsPresent[c]) {
				chars[n]=(char)c;
				charIndices[c]=n;
				n+=1;
			}
		}
	}

	/** Set special character that separates sequences. This character is
	 *  NOT part of the alphabet. It is numerically represented by -1. */
	public void setSeparator(char separator) {
		if (getIndex(separator)>=0) throw new IllegalArgumentException("Separator must not be contained in alphabet.");
		this.separator = separator;
		this.useSeparator = true;
	}

	private class ArrayIterator implements Iterator<Character> {
		private int i;
		ArrayIterator() { i=0; }
		public boolean hasNext() { return i<chars.length; }
		public Character next() {
			try {
				return chars[i++];
			} catch (IndexOutOfBoundsException e) {
				throw new NoSuchElementException();
			}
		}
		public void remove() { throw new UnsupportedOperationException(); }
	}
	
	public Iterator<Character> iterator() { return new ArrayIterator(); }
	
	public int size() { return chars.length; }
	
	public char get(int index) { return chars[index]; }
	
	/**
	 * @param set a set of characters
	 * @return a set containing characters of this alphabet which are not present in the given set.
	 */
	public Set<Character> getComplementSet(Set<Character> set) {
		Set<Character> complementSet = new TreeSet<Character>(); 
		for(char c : chars) {
			if(!set.contains(c)) {
				complementSet.add(c);
			}
		}
		return complementSet;
	}
	
	public int getIndex(char c) { return charIndices[c]; }
	public boolean contains(char c) { return charIndices[c]>=0; }

	/** Given an array of character indices, this methods returns the 
	 *  corresponding string. */
	public String buildString(int[] indices) {
		StringBuilder sb = new StringBuilder(indices.length);
		for (int c : indices) {
			if (useSeparator && (c==-1)) sb.append(separator);
			else sb.append(chars[c]);
		}
		return sb.toString();
	}

	/** Reverse function to buildString(). */
	public int[] buildIndexArray(String s) {
		return buildIndexArray(s,false);
	}
	
	/** Reverse function to buildString(). */
	public int[] buildIndexArray(String s, boolean appendMinusOne) {
		int[] result = new int[appendMinusOne?s.length()+1:s.length()];
		for (int i=0; i<s.length(); ++i) {
			if (useSeparator && (s.charAt(i)==separator)) {
				result[i] = -1;	
			} else {
				int c = charIndices[s.charAt(i)];
				if (c<0) throw new IllegalArgumentException("Unknown character: " + s.charAt(i));
				result[i] = c;
			}
		}
		if (appendMinusOne) result[s.length()] = -1;
		return result;
	}

	
	@Override
	public boolean equals(Object obj) {
		if (!(obj instanceof Alphabet)) return false;
		return Arrays.equals(chars, ((Alphabet)obj).chars);
	}

	@Override
	public int hashCode() {
		return Arrays.hashCode(chars);
	}
	
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("{ ");
		for(char c : this) {
			sb.append(c);
			sb.append(" ");
		}
		sb.append("}");
		return sb.toString();	
	}
	
}
